package leetcode.tree;

import java.util.Objects;

/**
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 * <p>
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 * <p>
 * 层次遍历带空值节点序列化
 */
public class LeetCode297_Codec2 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder r = new StringBuilder();
        TreeNode[] tn = new TreeNode[10001];

        int p = 0, q = 0;
        tn[q++] = root;
        r.append(tn[0].val).append(",");

        int len;
        while (p < q) {
            len = q - p;
            for (int i = 0; i < len; i++) {
                TreeNode t = tn[p++];
                if (t.left != null) {
                    tn[q++] = t.left;
                    r.append(t.left.val).append(",");
                } else {
                    r.append("#,");
                }
                if (t.right != null) {
                    tn[q++] = t.right;
                    r.append(t.right.val).append(",");
                } else {
                    r.append("#,");
                }
            }
        }
        return r.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] s = data.split(",");
        TreeNode[] tn = new TreeNode[10001];
        int p = 0, q = 0;
        int curIndex = 0;
        tn[q++] = new TreeNode(Integer.parseInt(s[curIndex++]));
        while (p < q) {

            TreeNode curNode = tn[p++];

            String l = s[curIndex++];
            String r = s[curIndex++];

            if (!Objects.equals(l, "#")) {
                TreeNode treeNode = new TreeNode(Integer.parseInt(l));
                tn[q++] = treeNode;
                curNode.left = treeNode;
            }
            if (!Objects.equals(r, "#")) {
                TreeNode treeNode = new TreeNode(Integer.parseInt(r));
                tn[q++] = treeNode;
                curNode.right = treeNode;
            }
        }

        return tn[0];
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);

        t1.left = t2;
        t3.left = t4;

        t1.right = t3;
        t3.right = t5;

        LeetCode297_Codec2 leetCode297Codec = new LeetCode297_Codec2();
        String serialize = leetCode297Codec.serialize(t1);
        System.out.println("serialize = " + serialize);
        TreeNode deserialize = leetCode297Codec.deserialize("1,2,3,#,#,4,5,#,#,#,#,");
        System.out.println("deserialize = " + deserialize);

    }

}
